package com.LeetCode.String;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 分割回文串
 */
public class SplitPalindromeStr {

    List<List<String>> res = new ArrayList<>();

    boolean[][] dp;

    public List<List<String>> partition(String s) {
        int len = s.length();
        if(len == 0)
            return res;

        dp = new boolean[len][len];

        for(int right = 0; right<len; right++){
            for(int left = 0; left <= right; left++){
                if(s.charAt(left) == s.charAt(right) && (right - left < 2 || dp[left+1][right-1]))
                    dp[left][right] = true;
            }
        }

        Deque<String> stack = new ArrayDeque<>();
        backtracking(s, 0, len, stack);
        return res;
    }

    private void backtracking(String s, int start, int len, Deque<String> path){
        if(start == len){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = start; i<len; i++){
            if(!dp[start][i])
                continue;
            path.addLast(s.substring(start, i+1));
            backtracking(s, i+1, len, path);
            path.removeLast();
        }
    }

    @Test
    public void test(){
        partition("aab").forEach(System.out::println);
    }
}



















